// * 递归：表示从自身调用函数（译注：也就是自调用）
// 函数调用自身时，我们称其为 递归步骤 每一步都存储在 堆栈 中，直到达到出口条件不需要再进行进一步调用为止。

// 1. 使用for循环实现
console.log(pow1(2, 3)) // 8

function pow1(x, n) {
	let result = 1

	for (let i = 0; i < n; i++) {
		result *= x
	}

	return result
}

// 2. 使用递归实现
console.log(pow2(2, 3)) // 8

function pow2(x, n) {
	if (n === 1) {
		return x
	} else {
		return x * pow2(x, n - 1)
	}
}

// 1. 递归调用 pow 函数（自身）时，首先当前函数会被暂停不会立即返回结果；
// 2. 然后函数在没有到达出口条件时，会将创建的子调用推入堆栈中（后进先出的原则执行）；
// 3. 当自调用函数达到出口条件时，它将返回一个结果给最后一个子调用函数，然后再依次执行堆栈中存储的其他子调用函数并将结果返回给前一个子调用函数；
// 4. 最后，当所有子调用函数都执行完毕后，函数将得到最终结果。

// 上面递归代码执行过程如下：
// 第一次调用：x * pow(x, n - 1) 此时 n = 3 -> [2 * pow(2, 3)]
// 第二次调用：x * pow(x, n - 1) 此时 n - 1，即 2 -> [2 * pow(2, 2)]
// 第三次调用：x * pow(x, n - 1) 此时 n - 1，即 1 -> [pow(2, 1)]
/*
  第三次调用时：n === 1 满足出口条件，不会继续产生子调用。返回 x，即 2。
  然后 2 返回给第二次的子调用函数，即 2 * 2 = 4，
  然后 4 返回给第一次的子调用函数，即 2 * 4 = 8，
  最终返回 8。
*/

// *********************************************************************************

// * 执行上下文和堆栈

// * 函数执行过程的相关信息被存储在 “执行上下文” 中。
// * “执行上下文” 是一个内部数据结构，它包含有关函数执行时的详细细节：当前控制流所在的位置，当前的变量，this 的值，以及一些其他内部细节。
// * 一个函数调用仅具有一个与其相关联的 “执行上下文”。
// * 当我们完成子调用后 —— 很容易恢复上一个上下文，因为它既保留了变量，也保留了当时所在代码的确切位置。

// * 当前一个函数进行嵌套调用时，将发生以下事儿：
// * 1. 当前函数被暂停；
// * 2. 与它关联的执行上下文被一个叫做 “执行上下文堆栈” 的特殊数据结构保存（记录在堆栈的顶部）；
// * 3. 执行嵌套调用；
// * 4. 嵌套调用结束后，从堆栈中恢复之前的执行上下文，并从停止的位置恢复外部函数。

// * 请注意内存要求。上下文占用内存，在我们的示例中，求 n 次方需要存储 n 个上下文，以供更小的 n 值进行计算使用。 任何递归都可以用循环来重写。通常循环变体更有效。

// *********************************************************************************

// * 递归遍历（迭代）。

// 使用递归实现（迭代）遍历，处理多层级结构数据。比常规循环方式更简洁和优雅。

// *********************************************************************************

// * 链表

// 链表数据结构，比常规数组的优势在于，对于首端（除末尾以外的元素）的元素进行插入/删除时效率更高。因为不会对后面的其他元素进行重排。

// * 链表元素：是使用 value 和 next（属性引用下一个 链表元素 或代表末尾的 null）。

// 例如：
let list = {
	value: 1,
	next: {
		value: 2,
		next: {
			value: 3,
			next: {
				value: 4,
				next: null,
			},
		},
	},
}

// 一段用来创建链表的代码：
let lists = { value: 1 }
lists.next = { value: 2 }
lists.next.next = { value: 3 }
lists.next.next.next = { value: 4 }
lists.next.next.next.next = null

// 在头部插入新的元素：
lists = { value: 'new item', next: lists }

console.log(lists)

// 删除中间的任意一个元素：
lists.next = lists.next.next // 这里删除了 { value: 1 } 直接返回 value: 1 中的 next 对象，也就是从 { value: 2 } 开始的对象。

console.log(lists)
